import java.security.interfaces.RSAKey;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

/*
 * @lc app=leetcode.cn id=501 lang=java
 *
 * [501] 二叉搜索树中的众数
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // Map<Integer,Integer>map=new HashMap<>();
    // public int[] findMode(TreeNode root) {
    //     dfs(root);
    //     List<Map.Entry<Integer,Integer>>list=new ArrayList<>(map.entrySet());
    //     Collections.sort(list,new Comparator<Map.Entry<Integer,Integer>>() {
    //         @Override
    //         public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
    //             return o2.getValue()-o1.getValue();
    //         }
    //     });//按value降序
    //     List<Integer> resList=new ArrayList<>();
    //     resList.add(list.get(0).getKey());
    //     int maxCount=list.get(0).getValue();
    //     for(int i=1;i<list.size();i++){
    //         if(list.get(i).getValue()==maxCount){
    //             resList.add(list.get(i).getKey());
    //         }
    //     }
    //     return resList.stream().mapToInt(Integer::intValue).toArray();//list转int数组
    // }

    // public void dfs(TreeNode root){
    //     if(root==null) return;
    //     dfs(root.left);
    //     map.put(root.val, map.getOrDefault(root.val, 0)+1);
    //     dfs(root.right);
    // }
    List<Integer> list;
    TreeNode pre;
    int maxCount;
    int count;
    public int[] findMode(TreeNode root) {
        list=new ArrayList<>();
        pre=null;
        maxCount=0;
        count=0;
        dfs(root);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    public void dfs(TreeNode root){
        if(root==null) return;
        dfs(root.left);
        if(pre==null||pre.val!=root.val) count=1;//第一次or重新计数
        if(pre!=null&&pre.val==root.val){
            count++;
        }
        //更新maxCount
        if(count==maxCount){
            list.add(root.val);
        }else if(count>maxCount){
            maxCount=count;
            list.clear();
            list.add(root.val);
          
        }
        pre=root;//利用前一个节点
        dfs(root.right);
    }
}
// @lc code=end

